package day73;

import java.time.temporal.Temporal;
import java.util.*;
import java.util.jar.Attributes;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
    public List<Integer> preorderTraversal(TreeNode root) {
//        Stack<TreeNode> stack = new Stack<>();
//        List<Integer> ans = new ArrayList<>();
//        while (root!=null || !stack.isEmpty()) {
//            ans.add(root.val);
//            if(root.right !=null) {
//                stack.push(root.right);
//            }
//            if(root.left !=null) {
//                stack.push(root.left);
//            }
//            root = null;
//            if(!stack.isEmpty()) {
//                root = stack.pop();
//            }
//        }
//        return ans;
        List<Integer> ans = new ArrayList<>();
        if(root == null) return ans;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode p = stack.pop();
            ans.add(p.val);
            if(p.right!=null) stack.push(p.right);
            if(p.left!=null) stack.push(p.left);
        }
        return ans;
    }
    public List<Integer> postorder(Node root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Deque<Node> stack = new ArrayDeque<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            for (Node item : node.children) {
                stack.push(item);
            }
        }
        Collections.reverse(res);
        return res;
    }
    public List<Integer> preorder(Node root) {
        // N叉树的前序遍历
        Stack<Node> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();
        // 先值后左子树后右子树
        while (root!=null || !stack.isEmpty()) {
            ans.add(root.val);
            for (int i = root.children.size()-1; i >=0 ; i--) {
                stack.push(root.children.get(i));
            }
            root = stack.pop();
        }
        return ans;
    }
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return Integer.toString(root.val);
        }
        if (root.right == null) {
            return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuffer().append(root.val).append("(").append(tree2str(root.left)).append(")(").append(tree2str(root.right)).append(")").toString();
    }
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 递归
//        if(root1 == null && root2 == null) {
//            return null;
//        }
//        if(root1 == null) {
//            TreeNode ans = new TreeNode(root2.val);
//            ans.left = mergeTrees(null,root2.left);
//            ans.right = mergeTrees(null,root2.right);
//            return ans;
//        }
//        if(root2 == null) {
//            TreeNode ans = new TreeNode(root1.val);
//            ans.left = mergeTrees(root1.left,null);
//            ans.right = mergeTrees(root1.right,null);
//            return ans;
//        }
//        TreeNode ans = new TreeNode(root1.val + root2.val);
//        ans.left = mergeTrees(root1.left,root2.left);
//        ans.right = mergeTrees(root1.right,root2.right);
//        return ans;
        if(root1 == null) return root2;
        if(root2 == null) return root1;

        TreeNode merged = new TreeNode(root1.val + root2.val);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(merged);
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(root1);
        queue2.offer(root2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if(left1!=null || left2!=null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1!=null) {
                    node.left = left1;
                } else if (left2 !=null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }
    public List<Double> averageOfLevels(TreeNode root) {
        // 二叉树的层平均值
        // 广度优先搜索
        List<Double> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            double av = 0;
            int t = queue.size();
            int count = t;
            while (t>0) {
                if(queue.peek().left!=null) {
                    queue.offer(queue.peek().left);
                }
                if(queue.peek().right!=null) {
                    queue.offer(queue.peek().right);
                }
                av+= queue.poll().val;
                t--;
            }
            ans.add(av/count);
        }
        return ans;
    }
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root!=null) {
            while (root!=null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        int i = 0,j = list.size()-1;
        while (i<j) {
            if(list.get(i) + list.get(j) < k) {
                i++;
            } else if (list.get(i) + list.get(j) > k) {
                j--;
            } else {
                return true;
            }
        }
        return false;
    }
    int ans = -1;
//    public int findSecondMinimumValue(TreeNode root) {
//        dfs(root, root.val);
//        return ans;
//    }
//    void dfs(TreeNode root, int cur) {
//        if (root == null) return ;
//        if (root.val != cur) {
//            if (ans == -1) ans = root.val;
//            else ans = Math.min(ans, root.val);
//            return ;
//        }
//        dfs(root.left, cur);
//        dfs(root.right, cur);
//    }
    public TreeNode searchBST(TreeNode root, int val) {
//        if(root == null) {
//            return null;
//        }
//        if(root.val == val) {
//            return root;
//        }
//        TreeNode ans = searchBST(root.left,val);
//        if(ans == null) {
//            ans = searchBST(root.right,val);
//        }
//        return ans;
//        if(root == null) return null;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        while (!queue.isEmpty()) {
//            if(queue.peek().val == val) {
//                return queue.peek();
//            }
//            if(queue.peek().left != null) {
//                queue.offer(queue.peek().left);
//            }
//            if(queue.peek().right != null) {
//                queue.offer(queue.peek().right);
//            }
//            queue.poll();
//        }
//        return null;
//        Stack<TreeNode> stack = new Stack<>();
//        while (root!=null || !stack.isEmpty()) {
//            while (root!=null) {
//                if(root.val == val) {
//                    return root;
//                }
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop().right;
//        }
//        return null;
        // 二叉搜索树
//        if(root == null) return null;
//        if(root.val < val) {
//            return searchBST(root.right,val);
//        } else if (root.val > val) {
//            return searchBST(root.left,val);
//        } else {
//            return root;
//        }
        while (root != null) {
            if(root.val > val) {
                root = root.left;
            } else if (root.val < val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
    class KthLargest {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        int k;
        public KthLargest(int k, int[] nums) {
            for (int x: nums) {
                priorityQueue.offer(x);
            }
            this.k = k;
        }

        public int add(int val) {
            // 堆
            priorityQueue.offer(val);
            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
            return priorityQueue.peek();
        }
    }
    public int minDiffInBST(TreeNode root) {
        // 二叉搜索树
//        int min = Integer.MAX_VALUE;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode pre = null;
//        while (root!=null || !stack.isEmpty()) {
//            while (root != null) {
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop();
//            if(pre == null) {
//                pre = root;
//            } else {
//                min = Math.min(min,root.val - pre.val);
//                pre = root;
//            }
//            root = root.right;
//        }
//        return min;
        TreeNode pre = null;
        int ans = Integer.MAX_VALUE;
        while (root != null) {
            if(root.left != null) {
                TreeNode p = root.left;
                while (p.right != null && p.right != root) {
                    p = p.right;
                }
                if(p.right == null) {
                    p.right = root;
                    root = root.left;
                } else {
                    if(pre != null) {
                        ans = Math.min(ans,root.val - pre.val);
                    }
                    pre = root;
                    root = root.right;
                    p.right = null;
                }
            } else {
                if(pre != null) {
                    ans = Math.min(ans,root.val - pre.val);
                }
                pre = root;
                root = root.right;
            }
        }
        return ans;
    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        getLeaf(root1,list1);
        getLeaf(root2,list2);
        if(list1.size() != list2.size()) return false;
        for (int i = 0; i < list1.size(); i++) {
            if(list1.get(i) != list2.get(i)) return false;
        }
        return true;
    }
    private void getLeaf(TreeNode root,List<Integer> list) {
        if(root.left == null && root.right == null) {
            list.add(root.val);
            return;
        }
        getLeaf(root.left,list);
        getLeaf(root.right,list);
    }
    public int maxProfit(int[] prices) {
        //
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
    public TreeNode increasingBST(TreeNode root) {
        TreeNode dummy = new TreeNode();
        TreeNode p = dummy;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            p.right = root;
            p = p.right;
            p.left = null;
            root = root.right;
        }
        return dummy.right;
    }
    public int rangeSumBST(TreeNode root, int low, int high) {
//        int ans = 0;
//        if(root == null) return 0;
//        if(root.val < low) {
//            ans += rangeSumBST(root.right,low,high);
//        } else if (root.val > high) {
//            ans += rangeSumBST(root.left,low,high);
//        } else {
//            ans = root.val + rangeSumBST(root.left,low,high) + rangeSumBST(root.right,low,high);
//        }
//        return ans;
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            if(queue.peek().left != null) {
                queue.offer(queue.peek().left);
            }
            if(queue.peek().right != null) {
                queue.offer(queue.peek().right);
            }
            if(queue.peek().val >= low && queue.peek().val <= high) {
                ans += queue.peek().val;
            }
            queue.poll();
        }
        return ans;
    }
    public boolean isUnivalTree(TreeNode root) {
//        if(root == null) return true;
//        Queue<TreeNode> queue = new LinkedList<>();
//        queue.offer(root);
//        int target = root.val;
//        while (!queue.isEmpty()) {
//            if(queue.peek().val != target) return false;
//            if(queue.peek().left != null) queue.offer(queue.peek().left);
//            if(queue.peek().right != null) queue.offer(queue.peek().right);
//            queue.poll();
//        }
//        return true;
//        if(root == null) return true;
//        int target = root.val;
//        Stack<TreeNode> stack = new Stack<>();
//        while (root!=null || !stack.isEmpty()) {
//            while (root != null) {
//                if(root.val != target) return false;
//                stack.push(root);
//                root = root.left;
//            }
//            root = stack.pop().right;
//        }
//        return true;
//        if(root == null) return true;
//        if(root.left != null) if(root.left.val != root.val) return false;
//        if(root.right != null) if(root.right.val != root.val) return false;
//        return isUnivalTree(root.left) && isUnivalTree(root.right);
//        if(root == null) return true;
//        int target = root.val;
//        while (root != null) {
//            if(root.left != null) {
//                TreeNode prev = root.left;
//                while (prev.right != null && prev.right != root) {
//                    prev = prev.right;
//                }
//                if (prev.right != null) {
//                     prev.right = null;
//                     if (root.val != target) return false;
//                     root = root.right;
//                } else {
//                    prev.right = root;
//                    root = root.left;
//                }
//            } else {
//                if(root.val != target) return false;
//                root = root.right;
//            }
//        }
//        return true;
        if(root == null) return true;
        int target = root.val;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val != target) return false;
            root = root.right;
        }
        return true;
    }
    class Pair {
        TreeNode parent;
        TreeNode node;
        TreeNode left;
        TreeNode right;
        int val;
        public Pair(TreeNode parent, TreeNode node) {
            this.parent = parent;
            this.node = node;
            this.left = node.left;
            this.right = node.right;
            this.val = node.val;
        }
    }
    public boolean isCousins(TreeNode root, int x, int y) {
        Queue<Pair> queue = new LinkedList<>();
        if(root.left != null) {
            queue.offer(new Pair(root,root.left));
        }
        if(root.right != null) {
            queue.offer(new Pair(root,root.right));
        }
        while (!queue.isEmpty()) {
            Pair xPair = null;
            Pair yPair = null;
            int size = queue.size();
            while (size > 0) {
                Pair pair = queue.poll();
                if(pair.val == x) {
                    xPair = pair;
                } else if (pair.val == y) {
                    yPair = pair;
                }
                if(pair.left != null) queue.offer(new Pair(pair.node,pair.left));
                if(pair.right != null) queue.offer(new Pair(pair.node,pair.right));
                size--;
            }
            if(xPair !=null && yPair != null) {
                if (xPair.parent != yPair.parent) {
                    return true;
                } else {
                    return false;
                }
            }
        }
        return false;
    }
    public int sumRootToLeaf(TreeNode root) {
        int ans = 0;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                if(root.left == null && root.right == null) {
                    ans += root.val;
                }
                if(root.left != null) root.left.val += root.val*2;
                if(root.right != null) root.right.val += root.val*2;
                stack.push(root);
                root = root.left;
            }
            root = stack.pop().right;
        }
        return ans;
    }
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        //
//        Stack<TreeNode> stack = new Stack<>();
//        stack.push(cloned);
//        TreeNode p = cloned;
//        while (!stack.isEmpty() || p != null) {
//            while (p != null) {
//                if(p.val == target.val) return p;
//                stack.push(p);
//                p = p.left;
//            }
//            p = stack.pop().right;
//        }
//        return null;
        if(original == null || cloned == null) return null;
        if(original == target) return cloned;
        TreeNode ans = getTargetCopy(original.left,cloned.left,target);
        if(ans != null) return ans;
        ans = getTargetCopy(original.right,cloned.right,target);
        return ans;
    }
//    public int dfs(TreeNode root, int val) {
////        if (root == null) {
////            return 0;
////        }
////        val = (val << 1) | root.val;
////        if (root.left == null && root.right == null) {
////            return val;
////        }
////        return dfs(root.left, val) + dfs(root.right, val);
////        if(root == null) {
////            return 0;
////        }
////        val = val*2 + root.val;
////        if(root.left == null && root.right == null) {
////            return val;
////        }
////        return dfs(root.left,val) + dfs(root.right,val);
//    }
//
//    public boolean findTarget(TreeNode root, int k) {
//        Set<Integer> set = new HashSet<>();
//        return dfs(root,k,set);
//    }
//    private boolean dfs(TreeNode root,int target,Set<Integer> set) {
//        if(root == null) return false;
//        if(set.contains(target - root.val)) return true;
//        set.add(root.val);
//        return dfs(root.left,target,set) || dfs(root.right,target,set);
//    }


//    public List<Integer> postorder(Node root) {
//        List<Integer> list = new ArrayList<>();
//        dfs(root,list);
//        return list;
//    }
//    private void dfs(Node root,List<Integer> list) {
//        if(root == null) return;
//        for (Node n: root.children) {
//            dfs(n,list);
//        }
//        list.add(root.val);
//    }

//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        Stack<TreeNode> stack = new Stack<>();
//        String[] s1 = getList(root);
//        String[] s2 = getList(subRoot);
//        // KMP匹配
//        int[] next = getNext(s2);
//        for (int i = 0,j = 0; i < s1.length; i++) {
//            while (j>0 && !s1[i].equals(s2[j])) {
//                j = next[j-1];
//            }
//            if(s1[i].equals(s2[j])) {
//                j++;
//            }
//            if(j == s2.length) {
//                return true;
//            }
//        }
//        return false;
//    }
//    private int[] getNext(String[] s) {
//        int[] next = new int[s.length];
//        for (int i = 1,j = 0; i < s.length; i++) {
//            while (j>0 && !s[j].equals(s[i])) {
//                j = next[j-1];
//            }
//            if(s[j].equals(s[i])) {
//                j++;
//            }
//            next[i] = j;
//        }
//        return next;
//    }
//    private String[] getList(TreeNode root) {
//        List<String> ans = new ArrayList<>();
//        if(root == null) return new String[ans.size()];
//        ans.add(Integer.toString(root.val));
//        dfs(ans,root.left,true);
//        dfs(ans,root.right,false);
//        return ans.toArray(new String[ans.size()]);
//    }
//    private void dfs(List<String> list,TreeNode root,boolean l) {
//        if(root == null) {
//            list.add(l?"lnull":"rnull");
//            return;
//        }
//        list.add(Integer.toString(root.val));
//        dfs(list,root.left,true);
//        dfs(list,root.right,false);
//    }
//    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//        if(root == null) return false;
//        if(checkSame(root,subRoot)) {
//            return true;
//        } else {
//            return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
//        }
//    }
//    private boolean checkSame(TreeNode a,TreeNode b) {
//        if(a == null && b == null) {
//            return true;
//        } else if (a == null || b == null) {
//            return false;
//        } else if (a.val != b.val) {
//            return false;
//        } else {
//            return checkSame(a.left,b.left) && checkSame(a.right,b.right);
//        }
//    }
}
